package cn.dapeng.array;

import cn.dapeng.utils.BuilderArray;

/**
 * @BelongProject study
 * @BelongPackage cn.dapeng.array
 * @Description 给定一个乱序的数组，并且相邻的两个元素不相等
 * <p>
 * 求局部最小值的下标
 * 假定一个数组长度为N
 * 1.  array[0] < array[1]
 * 2. array[N - 1] < array[N-2]
 * 3. array[i - 1]> array[i] < array[i + 1]
 * 以上三种都是局部最小
 * @ClassName BSPartMinimum
 * @Author xupenghong
 * @Date 2024/9/6 14:05
 * @Version 1.0.0
 */
public class BSPartMinimum {

    public static int minimumIndex(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }
        if (array.length == 1) {
            return 0;
        }

        if (array[0] < array[1]) {
            return 0;
        }
        int left = 0, right = array.length - 1, answer = -1;
        if (array[right] < array[right - 1]) {
            return right;
        }

        while (left <= right) {
            int middle = (left + right) / 2;

            if (array[middle - 1] > array[middle] && array[middle] < array[middle + 1]) {
                return middle;
            }

            if (array[middle - 1] < array[middle]) {
                right = middle;
            } else if (array[middle] > array[middle + 1]) {
                left = middle;
            }
        }
        return answer;
    }

    public static boolean check(int[] array, int index) {

        if (index == 0) {
            return array[index] < array[index + 1];
        }

        if (index == array.length - 1) {
            return array[index] < array[index - 1];
        }

        return array[index] < array[index - 1] && array[index] < array[index + 1];
    }


    /**
     * 很酷
     *
     * @param array
     * @param index
     * @return
     */
    public static boolean check2(int[] array, int index) {
        if (index == 0) {
            return array[index] < array[index + 1];
        }

        boolean leftBigger = index - 1 > 0 ? array[index - 1] > array[index] : true;
        boolean rightBigger = index + 1 < array.length ? array[index] < array[index + 1] : true;
        return leftBigger && rightBigger;
    }

    public static void main(String[] args) {

        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            int[] array = BuilderArray.builderNearNotEqualArray(5, 100, 3, 20);

            int index = minimumIndex(array);
            if (!check2(array, index)) {
                System.out.println("Oops");
            }
        }

    }
}
